"""Given an array of integers, every element appears three times except for one. 
   Find that single one.
   Note:
   Your algorithm should have a linear runtime complexity. Could you implement it 
   without using extra memory?"""

class Solution:
    # @param A, a list of integer
    # @return an integer
    def singleNumber(self, A):
        ones=0
        twos=0
        threes=0
        for i in A:
            twos |= (i & ones)
            ones ^= i     
            threes = (ones & twos)
            ones &= ~threes
            twos &= ~threes
        return ones
test = Solution()
A = [2,2,3,2]
print test.singleNumber(A)
             